package ToYesterday.duplicateNumbers_03;

//长度为n的数组里所有的数都在0~n-1内，求重复的数字
public class SolutionByMerge {

    //    @Test
//    public void testSort(){//这里测试归并排序是否正确
//        int[] nums = {4,1,2,7};
//        sort(nums,0,3);
//        System.out.println(Arrays.toString(nums));
//    }
    public int solutionByMerge(int[] nums) {
        sort(nums, 0, nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]==nums[i+1]){
                return nums[i];
            }
        }
        return 0;
    }

    public void sort(int[] nums, int front, int rear) {
        if (front == rear) {
            return;
        }
        int mid = (front + rear) / 2;
        sort(nums, front, mid);
        sort(nums, mid + 1, rear);
        merge(nums, front, mid, rear);

    }

    public void merge(int[] nums, int front, int mid, int rear) {
        int startRear = mid + 1;
        int[] numsTemp = new int[rear - front + 1];
        int k = 0;
        int frontTemp = front;
        int startRearTemp = startRear;
        while (frontTemp <= mid && startRearTemp <= rear) {
            if (nums[frontTemp] < nums[startRearTemp]) {
                numsTemp[k] = nums[frontTemp];
                frontTemp++;
                k++;
            } else {
                numsTemp[k] = nums[startRearTemp];
                startRearTemp++;
                k++;
            }
        }
        while (frontTemp <= mid) {
            numsTemp[k] = nums[frontTemp];
            frontTemp++;
            k++;
        }
        while (startRearTemp <= rear) {
            numsTemp[k] = nums[startRearTemp];
            startRearTemp++;
            k++;
        }
        k = 0;
        for (int i = front; i <= rear; i++) {
            nums[i] = numsTemp[k];
            k++;
        }
    }

}
